#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
typedef struct LinkNode{
	char data;
	struct LinkNode *next;
}*LiStack;
typedef struct Node{
	char data[20];
	struct Node *next;
}*DigitalStack;
typedef struct Grammar{
	char grammar[40]; //用来保存输入的文法
	struct Grammar *next; //用链表来保存文法
}Grammar;
typedef struct Char{//用于存放非终结字符和终结字符
	char Name;     //
	struct Char *next;
	char FirstVT[20];  //对于终结字符这一部分是空的
	char LastVT[20];	//对于终结字符这一部分是空的
	int FirstVTLength;
	int LastVTLength;
}Char;
typedef struct EqualRelative {
	char letf;
	char right;
	struct EqualRelative *next;
}EqualRelative;
char RelativeTable[20][20];
void InitStack(LiStack *s){
	printf("操作符栈初始化中....\n");
	//生成一个头结点
	*s = (LiStack) malloc(sizeof(struct LinkNode));
	if(*s == NULL){
		printf("malloc fail\n");
		exit(0);
	}
	printf("操作符栈=初始化成功！！\n");
	(*s)->next = NULL;
}
void InitDigitalStack(DigitalStack *s){
	printf("运算数栈初始化中....\n");
	//生成一个头结点
	*s = (DigitalStack) malloc(sizeof(struct Node));
	if(*s == NULL){
		printf("malloc fail\n");
		exit(0);
	}
	printf("运算数栈初始化成功！！\n");
	(*s)->next = NULL;
}
bool StackEmpty(LiStack S){
	if(S->next == NULL){ //如果头节点下一个节点为空，就可以说明这个栈为空栈
		return true;
	}
	else {
		return false;
	}
}
bool DigitalStackEmpty(DigitalStack S){
	if(S->next == NULL){ //如果头节点下一个节点为空，就可以说明这个栈为空栈
		return true;
	}
	else {
		return false;
	}
}
bool Push(LiStack S,char x){
	LiStack newNode = (LiStack) malloc(sizeof(struct LinkNode));
	newNode->data = x;
	//头插法
	newNode->next = S->next;
	S->next = newNode;
	return true;
}
bool DigitalStackPush(DigitalStack S,char x[]){
	DigitalStack newNode = (DigitalStack) malloc(sizeof(struct Node));
	strcpy(newNode->data, x);
	//newNode->data = x;
	//头插法
	newNode->next = S->next;
	S->next = newNode;
	return true;
}
bool DigitalStackPop(DigitalStack S,char *x){
	if(DigitalStackEmpty(S)){
		return false;
	}
	DigitalStack temp = NULL;
	strcpy(x, S->next->data);
	//删除栈顶元素节点
	temp = S->next;
	S->next = temp->next;
	free(temp);
	return true;
}
bool Pop(LiStack S,char *x){
	if(StackEmpty(S)){
		return false;
	}
	LiStack temp = NULL;
	*x = S->next->data;
	//删除栈顶元素节点
	temp = S->next;
	S->next = temp->next;
	free(temp);
	return true;
}
char GetTop(LiStack S){
	if(StackEmpty(S)){
		return '\0';
	}
	return S->next->data;
}

void GrammarListInit(Grammar **g){
	//这个只是用来生成头结点的，不存储文法内容
	*g = (Grammar*) malloc(sizeof(Grammar));
	(*g)->next = NULL;
}
void CharListInit(Char **s){
	*s = (Char*) malloc(sizeof(Char));
	(*s)->next = NULL;
}
void EqualRelativeListInit(EqualRelative **EqualList){
	//这个只是用来生成头结点的，不存储文法内容
	*EqualList = (EqualRelative*) malloc(sizeof(Grammar));
	(*EqualList)->next = NULL;
}
void InsertGrammar(Grammar *g,char grammar[]){  //输入文法内容
	Grammar *newNode = (Grammar*) malloc(sizeof(Grammar));
	//这里采用头插法创建
	newNode->next = g->next;
	g->next = newNode;
	strcpy(newNode->grammar, grammar);
}
Char* InsertChar(Char *CharList,char name){  //增加字符
	Char *newNode = (Char*) malloc(sizeof(Char));
	//这里采用头插法创建
	newNode->next = CharList->next;
	newNode->FirstVTLength = 0;
	newNode->LastVTLength = 0;
	CharList->next = newNode;
	newNode->Name = name;
	return newNode;
}
EqualRelative* InsertEqualRelative(EqualRelative *EqualRelativeList,char left,char right){  //增加相对的运算关系
	EqualRelative *newNode = (EqualRelative*) malloc(sizeof(EqualRelative));
	//这里采用头插法创建
	newNode->next = EqualRelativeList->next;
	EqualRelativeList->next = newNode;
	newNode->letf = left;
	newNode->right = right;
	return newNode;
}
void PrintGrammar(Grammar *g){
	Grammar *p = g->next;
	while (p) {
		printf("%s\n",p->grammar);
		p = p->next;
	}
}
Char* SearchCharByName(Char *CharList,char name){
	Char *p = CharList->next;
	while (p) {
		if(p->Name == name){
			return p;
		}
		p = p->next;
	}
	return NULL;//表示没有找到这个
}
//用于从文法中找到非终结字符和终结字符
void LookThroughGrammarList(Grammar *g,Char *TerminalCharList,Char *NoTerminalCharList){
	Grammar *p = g->next;
	while (p) {
		//插入非终结字符到非终结字符列表
		if(SearchCharByName(NoTerminalCharList, p->grammar[0]) == NULL){
			InsertChar(NoTerminalCharList,p->grammar[0]);
		}
		p = p->next;
	}
	p = g->next;
	while (p) {
		for(int i=3;i<strlen(p->grammar);i++){
			if(SearchCharByName(NoTerminalCharList, p->grammar[i]) == NULL && p->grammar[i] != '|'){
				if(SearchCharByName(TerminalCharList, p->grammar[i]) == NULL){
					InsertChar(TerminalCharList,p->grammar[i]);
				}
			}
		}
		p = p->next;
	}
}
void PrintChar(Char *g){
	Char *p = g->next;
	while (p) {
		printf("%c   ",p->Name);
		p = p->next;
	}
}
void PrintFirstVT(Char *g){
	Char *p = g->next;
	printf("FIRSTVT集：\n");
	while (p) {
		printf("%c:",p->Name);
		for(int i=0;i<p->FirstVTLength;i++){
			printf("%c ",p->FirstVT[i]);
		}
		printf("\n");
		p = p->next;
	}
}
void PrintLastVT(Char *g){
	Char *p = g->next;
	printf("LASTVT集：\n");
	while (p) {
		printf("%c:",p->Name);
		for(int i=0;i<p->LastVTLength;i++){
			printf("%c ",p->LastVT[i]);
		}
		printf("\n");
		p = p->next;
	}
}
void PrintEqual(EqualRelative *g){
	EqualRelative *p = g->next;
	while (p) {
		printf("left: %c  |right: %c \n",p->letf,p->right);
		p = p->next;
	}
}
void FindEqualRelative(Grammar *g,EqualRelative *EqualRelativeList,Char *TerminalCharList){
	Grammar *p = g->next;
	bool lock = false;
	char pre,behind;
	while (p) {
		lock = false;
		for(int i=3;i<strlen(p->grammar);i++){
			//这里求等于的优先级可能存在点问题
			if(SearchCharByName(TerminalCharList,p->grammar[i]))
			{
				if(lock){
					behind = p->grammar[i];
					//printf("  %c %c\n",pre,behind);
					InsertEqualRelative(EqualRelativeList, pre, behind);
					break;
				}
				pre = p->grammar[i];
				lock = true;
			}
			else if(p->grammar[i] =='|'){
				lock = false;
			}
		}
		p = p->next;
	}
}
void FindFirstVT(Grammar *g,Char *NoTerminalCharList,Char *TerminalCharList){
	Grammar *p = g->next;
	Char *NoTerminalChar = NULL;
	char firstVTItem;
	bool lock = false;//是否是第一次出现;
	while (p) {
		lock = false;
		NoTerminalChar = SearchCharByName(NoTerminalCharList, p->grammar[0]);
		for(int i=3;i<strlen(p->grammar);i++){
			if(SearchCharByName(TerminalCharList,p->grammar[i])){
				//如果该字符是终结字符
				if(!lock){
					//如果没有锁，就说明这是我们要找到第一个终结字符
					firstVTItem = p->grammar[i];
					//加锁保护
					NoTerminalChar->FirstVT[NoTerminalChar->FirstVTLength++] = firstVTItem;
					lock = true;
				}
			}
			else if(p->grammar[i] == '|'){
				//遇到|就解锁
				lock = false;
			}
		}
		p = p->next;
	}
}
void CreateTable(Grammar *g,EqualRelative *Equal,Char *NoTerminalCharList,Char *TerminalCharList){
    Char *p = TerminalCharList->next;
	int left = 1,right = 1; //left == First  right== Last
	while (p) {
		//把终结符存入到边线上
		RelativeTable[0][right++] = p->Name; 
		RelativeTable[left++][0] = p->Name; 
		RelativeTable[0][right] = '\0';
		RelativeTable[left][0] = '\0';
		p = p->next;
	}
	EqualRelative *e = Equal->next; 
	while (e) {
		int x,y;
		for(x=1;RelativeTable[0][x]!='\0';x++){
			if(e->right ==RelativeTable[0][x]){
				break;
			}
		}
		for(y=1;RelativeTable[y][0]!='\0';y++){
			if(e->letf ==RelativeTable[y][0]){
				break;
			}
		}
		//反了这里
		RelativeTable[y][x] = '=';
		e = e->next;
	}
	//根据语法和FRISTVT和LASTVT创建表
	Grammar *t = g->next;
	while(t){
		for(int i=3;i<strlen(t->grammar);i++){
			//FIRSTVT
		Char *ch = SearchCharByName(TerminalCharList, t->grammar[i]);
			//如果是终结字符
			if(ch){
				//printf("终结字符1\n");
				//如果是非终结字符
				Char *ch2 = SearchCharByName(NoTerminalCharList, t->grammar[i+1]);
				if(ch2){
					//是我们要找的
					//printf("非终结字符2\n");
					int j;
					for(j=1;RelativeTable[j][0] != '\0';j++)
						if(RelativeTable[j][0]== ch->Name){
							break;
						}
					//printf("j = %d\n",j);
					//找到第几列
					for(int n=0;n<ch2->FirstVTLength;n++){
						for(int m=1;RelativeTable[0][m]!='\0';m++){
							if(RelativeTable[0][m] == ch2->FirstVT[n]){
								RelativeTable[j][m] = '>';
							}
						}
					}
			}
			}		//LASTVT
			//如果是非终结字符
			ch = SearchCharByName(NoTerminalCharList, t->grammar[i]);
			if(ch){
				//如果是终结字符
				Char *ch2 = SearchCharByName(TerminalCharList, t->grammar[i+1]);
				//printf("非终结字符\n");
				if(ch2){
					//是我们要找的
					//printf("非终结字符2\n");
					int j;
					for(j=1;RelativeTable[0][j] != '\0';j++)
						if(RelativeTable[0][j]== ch2->Name){
							break;
						}
					//printf("j = %d\n",j);
					//找到第几列
					for(int n=0;n<ch->LastVTLength;n++){
						for(int m=1;RelativeTable[m][0]!='\0';m++){
							if(RelativeTable[m][0] == ch->LastVT[n]){
								RelativeTable[m][j] = '<';
							}
						}
					}
				}
			}
		}
		t = t->next;
	}
}
//没写好，有太多的if else
void FindLastVT(Grammar *g,Char *NoTerminalCharList,Char *TerminalCharList){
	Grammar *p = g->next;
	Char *NoTerminalChar = NULL;
	char firstVTItem;
	char RelativeTable[20][20];
	bool lock = false;//是否是第一次出现;
	while (p) {
		lock = false;
		NoTerminalChar = SearchCharByName(NoTerminalCharList, p->grammar[0]);
		Char *temp =  SearchCharByName(NoTerminalCharList, p->grammar[strlen(p->grammar)-1]);
		if(temp) {
			strcpy(NoTerminalChar->LastVT, temp->LastVT);
			NoTerminalChar->LastVTLength = temp->LastVTLength;
		}
		for(int i=3;i<strlen(p->grammar);i++){
			if(SearchCharByName(NoTerminalCharList,p->grammar[i])&&!lock){
				//加锁
				lock = true;
			}
			else if(SearchCharByName(TerminalCharList,p->grammar[i])&&lock){
				//printf("%c\n",p->grammar[i]);
				NoTerminalChar->LastVT[NoTerminalChar->LastVTLength++] = p->grammar[i];
				lock = false;
			}
			else if(p->grammar[i-1] == '|'&&p->grammar[i+1]=='|'&&SearchCharByName(TerminalCharList,p->grammar[i])){
				NoTerminalChar->LastVT[NoTerminalChar->LastVTLength++] = p->grammar[i];
				lock = false;
			}
			else if( i == strlen(p->grammar) -1&&SearchCharByName(TerminalCharList,p->grammar[i])){
				NoTerminalChar->LastVT[NoTerminalChar->LastVTLength++] = p->grammar[i];
				lock = false;
			}
			else if(p->grammar[i] == '|'){
				//遇到|就解锁
				lock = false;
			}
		}
		p = p->next;
	}
}
char getRelativeByTable(char inStackChar,char OutStackChar){
	//穿来一个栈外字符和栈内字符比较
	//首先找到行列
	int i,j;
	for(i=0;RelativeTable[i][0]!='\0';i++){
		if(RelativeTable[i][0] == inStackChar)
		{
			break;
		}
	}
	for(j=0;RelativeTable[0][j]!='\0';j++){
		if(RelativeTable[0][j] == OutStackChar)
			{
				break;
			}
	}
	return RelativeTable[i][j];
}
double CharTranslateToDouble(char str[]){
	int i;
	for( i =0;i<strlen(str);i++){
		if(str[i] == '.'){
			//找到小数点
			break;
		}
	}
	char temp[20] = {0};
	stpncpy(temp,str ,i);
	int integer = atoi(temp);//将小数点前面的整数保存好
	stpcpy(temp,str+i+1);
	double f = atof(temp);//将小数点后面几位转为浮点的整数形式
	double d = 1;
	for(i=1;i<strlen(temp)+1;i++){
		d *= 10;//计算要移动几位
	}
	f = f/d;//将小数点后移
	double result = f+integer;
	//printf("%f ",result+1);
	return result;
}
int  judgeCaculateType(char pre[],char behind[]){
	//判断一下两个的类型
	int flag = 0; //0 浮和浮  1 浮和整 2 整和浮  3整和整
	bool tag1 = false;
	bool tag2 = false;
	for(int i=0;i<strlen(pre);i++){
		if(pre[i]=='.'){
			tag1 = true;
		}
	}
	for(int i=0;i<strlen(behind);i++){
		if(pre[i]=='.'){
			tag2 = true;
		}
	}
	if(tag1&&tag2){
		//都是浮点数
		return 0;
	}
	else if(tag1&&!tag2){
		return 1;
	}
	else if(!tag1&&tag2){
		return 2;
	}
	else {
		return 3;
	}
}
char *CaculateDetail(char pre[],char behind[],char operate){
	//这里有四种情况 浮和浮 浮和整 整和浮 整和整 
	printf("%c\n",operate);
	double a,b,result;int c,d;char resultChar[20]; int intResult;
	memset(resultChar,0,sizeof(resultChar));
	switch (judgeCaculateType(pre, behind)) {
		case 0: //浮 和 浮 a  b
			a =  CharTranslateToDouble(pre);
			b =  CharTranslateToDouble(behind);
			if(operate == '+'){
				result = a+b;
			}
			else if(operate == '-'){
				result = a-b;
			}
			else if(operate == '*'){
				result = a*b;
			}
			else if(operate == '/'){
				result = a/b;
			}
			//计算结果转字符入栈
			sprintf(resultChar,"%.2lf",result);
			break;
		case 1: //浮 和 整 a c
			a =  CharTranslateToDouble(pre);
			c = atoi(behind);
			if(operate == '+'){
				result = a+c;
			}
			else if(operate == '-'){
				result = a-c;
			}
			else if(operate == '*'){
				result = a*c;
			}
			else if(operate == '/'){
				result = a/c;
			}
			//计算结果转字符入栈
			sprintf(resultChar,"%.2lf",result);
			sprintf(resultChar,"%.2lf",result);
			break;
		case 2://整 合 浮  c a
			c =  atoi(pre);
			a = CharTranslateToDouble(behind);
			if(operate == '+'){
				result = c+a;
			}
			else if(operate == '-'){
				result = c-a;
			}
			else if(operate == '*'){
				result = c*a;
			}
			else if(operate == '/'){
				result = c/a;
			}
			//计算结果转字符入栈
			sprintf(resultChar,"%.2lf",result);
			break;
		case 3://整和整  
			c =  atoi(pre);
			d =  atoi(behind);
			//计算结果转字符入栈
			c =  atoi(pre);
			a = CharTranslateToDouble(behind);
			if(operate == '+'){
				result = c+d;
			}
			else if(operate == '-'){
				result = c-d;
			}
			else if(operate == '*'){
				result = c*d;
			}
			else if(operate == '/'){
				result = c/d;
			}
			sprintf(resultChar,"%.2lf",result);
			break;
	}
	
	printf("%s %s\n",pre,behind);
	printf("%s\n",resultChar);
	return resultChar;
}
void Caculate(LiStack OperatorStack,DigitalStack digitalStack,char str[]){
	char temp;
	char data[20];
	int i,j;
	for(i=0;i<strlen(str);i++){
		//printf("%c",str[i]);
		if(isnumber(str[i])){
			int n = 0;
			//printf("%c ",str[i]);
			for(j=i;isnumber(str[j])||str[j] == '.';j++){
				data[n++] = str[j];
				data[n] = '\0';
			}
			//printf("%s",data);
			DigitalStackPush(digitalStack, data);
			i = j-1;
		}
		else if(!isnumber(str[i])){//操作符
			//printf("来了\n");
			if(!StackEmpty(OperatorStack)){
				//说明栈不空 比较后入栈
				temp = GetTop(OperatorStack);
				char result = getRelativeByTable(temp, str[i]);
				printf("%c \n",result);
				if(result == '=' || result == '<'){
					//入栈
					Push(OperatorStack, str[i]);
				}
				else if(result == '>'){
					//出栈运算
					char pre[20],behind[20],*operate;
					//printf("op:%c\n",*operate);
					Pop(OperatorStack,operate);
					DigitalStackPop(digitalStack, behind);
					DigitalStackPop(digitalStack, pre);
					DigitalStackPush(digitalStack,CaculateDetail(pre, behind,*operate));
					Push(OperatorStack, str[i]);
				}
				else {
					printf("语法错误！");
				}
			}
			else{
				//说明栈空、直接入栈  如果查到是 = 和<  关系就入栈，否则出栈运算
				Push(OperatorStack, str[i]);
			}
		}
	}
//	char pre[20],behind[20],*operate;
//	//printf("op:%c\n",*operate);
//	Pop(OperatorStack,operate);
//	DigitalStackPop(digitalStack, behind);
//	DigitalStackPop(digitalStack, pre);
//	DigitalStackPush(digitalStack,CaculateDetail(pre, behind,*operate));
}
int main(int argc, char *argv[]) {
	Grammar *g = NULL;
	LiStack OperatorStack = NULL;
	DigitalStack digitalStack = NULL;
	GrammarListInit(&g);
	InsertGrammar(g, "S->v=E");
	InsertGrammar(g, "E->E+E|E-E|E*E|E/E|(E)|v|i");
	Char *TerminalCharList = NULL; //终结字符列表
	Char *NoTerminalCharList = NULL;//非终结字符列表
	EqualRelative *EqualList = NULL;
	CharListInit(&TerminalCharList);
	CharListInit(&NoTerminalCharList);
	EqualRelativeListInit(&EqualList);
	LookThroughGrammarList(g,TerminalCharList,NoTerminalCharList);
	printf("\n终结字符集:\n");
	PrintChar(TerminalCharList);
	printf("\n非终结字符集:\n");
	PrintChar(NoTerminalCharList);
	printf("\n");
	FindEqualRelative(g,EqualList,TerminalCharList);
	PrintEqual(EqualList);
	FindFirstVT(g,NoTerminalCharList,TerminalCharList);
	FindLastVT(g,NoTerminalCharList,TerminalCharList);
	PrintFirstVT(NoTerminalCharList);
	PrintLastVT(NoTerminalCharList);
	
	for(int i=0;i<20;i++){
		for(int j=0;j<20;j++)
			RelativeTable[i][j]= '0';
	}
	CreateTable(g,EqualList,NoTerminalCharList,TerminalCharList);
	printf("算符优先级表:\n");
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++)
			printf("%c ",RelativeTable[i][j]);
		printf("\n");
		
	}
	//	printf("%c ",getRelativeByTable('v','='));
	InitStack(&OperatorStack);
	InitDigitalStack(&digitalStack);
	
	Caculate(OperatorStack,digitalStack,"2212.12+8721+2+233+343.3");
	//CharTranslateToDouble("21345.324");
}